77. Combinations
Medium

Given two integers n and k, return all possible combinations of k numbers out of the range [1, n].

You may return the answer in any order.

 

Example 1:

Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Example 2:

Input: n = 1, k = 1
Output: [[1]]

 

Constraints:

  • 1 <= n <= 20
  • 1 <= k <= n
Accepted
374,766
Submissions
637,252
Seen this question in a real interview before?
Companies
Related Topics
Similar Questions

Average Rating: 3.63 (40 votes)

Premium

Solution


Approach 1: Backtracking

Algorithm

Backtracking is an algorithm for finding all solutions by exploring all potential candidates. If the solution candidate turns to be not a solution (or at least not the last one), backtracking algorithm discards it by making some changes on the previous step, i.e. backtracks and then try again.

Here is a backtrack function which takes a first integer to add and a current combination as arguments backtrack(first, curr).

  • If the current combination is done - add it to output.

  • Iterate over the integers from first to n.

    • Add integer i into the current combination curr.

    • Proceed to add more integers into the combination : backtrack(i + 1, curr).

    • Backtrack by removing i from curr.

Implementation

Current
1 / 12

Complexity Analysis

  • Time complexity : O(kCNk)\mathcal{O}(k C_N^k), where CNk=N!(Nk)!k!C_N^k = \frac{N!}{(N - k)! k!} is a number of combinations to build. append / pop (add / removeLast) operations are constant-time ones and the only consuming part here is to append the built combination of length k to the output.

  • Space complexity : O(CNk)\mathcal{O}(C_N^k) to keep all the combinations for an output.


Approach 2: Lexicographic (binary sorted) combinations

Intuition

The idea here is not just to get the combinations but to generate them in a lexicographic sorted order.

postorder

Algorithm

The algorithm is quite straightforward :

  • Initiate nums as a list of integers from 1 to k. Add n + 1 as a last element, it will serve as a sentinel. Set the pointer in the beginning of the list j = 0.

  • While j < k :

    • Add the first k elements from nums into the output, i.e. all elements but the sentinel.

    • Find the first number in nums such that nums[j] + 1 != nums[j + 1] and increase it by one nums[j]++ to move to the next combination.

Implementation

Complexity Analysis

  • Time complexity : O(kCNk)\mathcal{O}(k C_N^k), where CNk=N!(Nk)!k!C_N^k = \frac{N!}{(N - k)! k!} is a number of combinations to build.

    The external while loop is executed CNkC_N^k times since the number of combinations is CNkC_N^k. The inner while loop is performed CNjkjC_{N - j}^{k - j} times for a given j. In average over CNkC_N^k visits from the external loop that results in less than one execution per visit.
    Hence the most consuming part here is to append each combination of length kk (CNkC_N^k combinations in total) to the output, that takes O(kCNk)\mathcal{O}(k C_N^k) time.

    You could notice that the second algorithm is much faster than the first one despite they both have the same time complexity. It's a consequence of dealing with the recursive call stack frame for the first algorithm, and the effect is much more pronounced in Python than in Java.

  • Space complexity : O(CNk)\mathcal{O}(C_N^k) to keep all the combinations for an output.

Links

Donald E. Knuth, The Art of Computer Programming, 4A (2011)

Report Article Issue

Comments: 39
mircules's avatar
Read More

Shouldn't the backtracking approach's space complexity be the same as the time complexity of O(k * nCk)? We have nCk subsets and they're all k in size

24
Show 2 replies
Reply
Share
Report
dylan20's avatar
Read More

solution 1 should return after appending a complete combination. otherwise the combination will grow beyond size K

37
Show 6 replies
Reply
Share
Report
tom53's avatar
Read More

Add return condition for approach1 (prune unused call stack).

class Solution:
      def combine(self, n: int, k: int) -> List[List[int]]:   
        def backtrack(first, curr):
            # if the combination is done
            if len(curr) == k:  
                output.append(curr[:])
                return
                
            if (k - len(curr)) > (n - first + 1):
                return
                
            for i in range(first, n + 1):
                # add i into the current combination
                curr.append(i)
                # use next integers to complete the combination
                backtrack(i + 1, curr)
                # backtrack
                curr.pop()
        
        output = []
        curr = []
        backtrack(1, curr)
        return output

11
Show 3 replies
Reply
Share
Report
v21's avatar
Read More

Approach 2 is not clear at all.

6
Reply
Share
Report
oceanpark13's avatar
Read More

The time complexity of O(KCn,k) is definitely wrong. For example, let K==N, then we have the time complexity to be O(N). However, in the first approach, it enumerates all 2^N combinations.

5
Show 2 replies
Reply
Share
Report
ShannonLn's avatar
Read More

In Approach 1, why output.append(curr[:]), not output.append(curr)? I know lists are referred by references, but cannot distinguish the use case in problems like this.

4
Show 2 replies
Reply
Share
Report
shakeri's avatar
Read More

The space complexity of backtracking should be O(k+Ckn)

5
Reply
Share
Report
Struggle20's avatar
Read More

"The idea here is not just to get the combinations but to generate them in a lexicographic sorted order." - not sure why the author says generations like [1,2] [1,3] [2,3] [1,4]...(as in the picture below) is a lexicographic sorted order.

3
Show 1 reply
Reply
Share
Report
purplebeth's avatar
Read More

why do we need to create a shallow copy of curr in the python solution? (curr[:])

3
Show 2 replies
Reply
Share
Report
kafola's avatar
Read More

Re approach #2, why are we setting nums[j] = j + 1 not to nums[j+1]?

1
Show 1 reply
Reply
Share
Report

You don't have any submissions yet.

/23
Contribute
|||
Saved
Trie
This list is empty.